package com.alt.www.find;

/**
 * Created by 27340 on 2017/9/16.是
 */
public class WeightedQuickUnionUF {
    private int[] id;
    private int[] sz;
    private int count;
    public WeightedQuickUnionUF(int N){
        count = N;
        id = new int[N];
        for (int i = 0; i <N ; i++) {
            id[N] = i;
        }
        sz = new int[N];
        for (int i = 0; i <N ; i++) {
            sz[N] = i;
        }
    }

    public int count(){
        return count;
    }

    public boolean connected(int p, int q){
        return find(p) == find(q);
    }

    public int find(int p){
        //跟随链接找到根节点
        while (p!=id[p]){
            p = id[p];
        }
        return p;
    }

    public void union(int p, int q){
        int i = find(p);
        int j = find(q);
        if(i==j)return;
        //将小树根结点加入到大树的根节点
        if(sz[i]<sz[j]){
            id[i] = j;
            sz[j] += sz[i];
        }else{
            id[j] = i;
            sz[i] += sz[j];
        }
        count--;
    }
}
